package LeetCode._02算法基础.day10递归回溯;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 21 - 16:38
 * @Description 给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
 * @Version 中等
 */
public class _47全排列2 {
    static int[] nums = {1, 1, 2};
    @Test
    public void test(){
        List<List<Integer>> res = permuteUnique(nums);
        System.out.println(res);
    }
    boolean[] vis;
    //设定一个规则，保证在填第i个数的时候重复数字只会被填入一次即可
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> perm = new ArrayList<>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            //该元素已取 或 与上个相同且上个元素未取 则跳过该元素
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }

            //取当前元素
            perm.add(nums[i]);
            vis[i] = true;
            //填充下一 位置
            backtrack(nums, ans, idx + 1, perm);

            //回溯
            vis[i] = false;
            perm.remove(idx);
        }
    }
}
